from typing import List
class Solution:
    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:
        def dfs(i,j,k):
            if i<0 or i>=len(grid) or j<0 or j>=len(grid[0]) or grid[i][j]!=target[k]:
                return False

            if k==len(target)-1:
                return True
            grid[i][j]=''
            ans=dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or dfs(i,j+1,k+1) or dfs(i,j-1,k+1)
            grid[i][j]=target[k]
            return ans
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if dfs(i,j,0):
                    return True
        return False